package com.justnow.offer;

import java.util.HashMap;
import java.util.Map;

public class Solution07 {
    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        Solution07 solution07 = new Solution07();
        solution07.reConstructBinaryTree(pre, in);
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in , 0, in.length - 1);
        return root;
    }

    private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        //1. 递归结束的条件
        if (startPre > endPre || startIn > endIn)
            return null;
        Map<Integer, Integer> map = new HashMap<>();
        TreeNode root = new TreeNode(pre[startPre]);

        //2. 将问题分解为子问题
        for (int i = startIn; i <= endIn; i++) {
            if (in[i] == pre[startPre]) {
                int leftStartPre = startPre + 1;
                int leftEndPre = startPre + i - startIn;
                int leftStartIn = startIn + 1;
                int leftEndIn = i - 1;
                root.left = reConstructBinaryTree(pre,leftStartPre, leftEndPre, in, leftStartIn, leftEndIn);
                root.right = reConstructBinaryTree(pre,leftEndPre + 1, endPre, in, i + 1, endIn);
                break;
            }
            
        }
        return root;
    }
}


